package io.tec.cloud.algorithm.c05_v20220617;

import io.tec.cloud.algorithm.AlgorithmUtil;

import java.util.Arrays;

/**
 * 33	05_3	05	3	05归并排序附加题、随机快速排序	O(N)复杂度完成荷兰国旗问题：小于X的放左边，等于X的放中间，大于X的放右边
 * <p>
 * 随机快排：
 * 1、在排序区间，随机一个索引，和区间内最后一个值交换；
 * 2、以N-1的值X为划分值，划分为<X；=X；>X三个区域
 *
 * @author tec-nine
 */
public class Code05_3_QuickSort {

    public static void quickSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {

        if (arr == null || arr.length < 2) {
            return;
        }

        if (l > r) {
            return;
        }
        // 边界：到不了R，(int) (l + Math.random() * (r - l))，[l, r)
        int randomIndex = (int) (l + Math.random() * (r - l));
        AlgorithmUtil.swap(arr, randomIndex, r);
        int[] equalsArea = partition(arr, l, r);
        process(arr, l, equalsArea[0] - 1);
        process(arr, equalsArea[1] + 1, r);
    }

    private static int[] partition(int[] arr, int l, int r) {

        int less = l - 1;
        int more = r;
        int index = l;
        // TODO 边界
        while (index < more) {
            if (arr[index] < arr[r]) {
                AlgorithmUtil.swap(arr, ++less, index++);
            } else if (arr[index] == arr[r]) {
                index++;
            } else if (arr[index] > arr[r]) {
                AlgorithmUtil.swap(arr, --more, index);
            }
        }
        // TODO arr[r]和大于区的第一个索引交换：使大于区向右移动一个位置
        AlgorithmUtil.swap(arr, r, more++);
        // 返回[小于区的下一个索引, 大于区的上一个索引]
        return new int[]{less + 1, more - 1};
    }


    public static void main(String[] args) {
        int testTimes = 100_0000;
        int maxValue = 100;
        int maxLength = 100;
        for (int t = 0; t < testTimes; t++) {
            int[] arr = AlgorithmUtil.generateArray(maxValue, AlgorithmUtil.randomWithoutTarget(maxLength));
            int[] arr1 = AlgorithmUtil.copyArray(arr);
            int[] arr2 = AlgorithmUtil.copyArray(arr);
            quickSort(arr1);
            Arrays.sort(arr2);
            if (!AlgorithmUtil.isEquals(arr1, arr2)) {
                AlgorithmUtil.printArray(arr);
                AlgorithmUtil.printArray(arr1);
                AlgorithmUtil.printArray(arr2);
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }
}
